package graph;

/**
 * O(v^2) Single source shortest path dijkstra solution
 * 
 * @author yinzichen
 * 
 */

class Dijkstra {
	private int[] prev;

	private static final int INF = Integer.MAX_VALUE;

	public int[] dijkstra(int[][] graph, int vertexNum, int source) {
		prev = new int[vertexNum];
		boolean[] visit = new boolean[vertexNum];
		int[] dist = new int[vertexNum];
		dist[source] = graph[source][source];
		prev[source] = -1;
		int min, u;
		for (int i = 1; i < vertexNum; i++) {
			min = INF;
			u = -1;
			for (int j = 0; j < vertexNum; j++)
				if (!visit[j] && dist[j] < min) {
					min = dist[j];
					u = j;
				}
			if (u == -1) {
				break;
			}
			visit[u] = true;
			for (int j = 0; j < vertexNum; j++)
				if (!visit[j] && graph[u][j] != INF
						&& dist[j] > dist[u] + graph[u][j]) {
					dist[j] = dist[u] + graph[u][j];
					prev[j] = u;
				}
		}
		return dist;
	}

	public int[] getPath() {
		return prev;
	}

}
